package com.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 39. 组合总和
 * <p>
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数================================
 * 解集不能包含重复的组合。
 * <p>
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 * [7],
 * [2,2,3]
 * ]
 */
public class Leet39 {
	public static void main(String[] args) {
//		new Leet39().combinationSum(new int[]{2,3,6,7},7);
		new Leet39().combinationSum(new int[]{2,3,5},8);
	}

	/**
	 * 40%,52%,我,回溯可以就是慢点,
	 * 优化
	 * 86%,90%,我
	 * 99%,96%,我
	 */
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> list=new ArrayList();
		if(candidates==null || candidates.length==0 ||target<=0)return list;//7.优化到99%

		Arrays.sort(candidates);
		List<Integer> l=new ArrayList();
		dp(list,l,candidates,target,candidates.length-1);
		return list;
	}

	/**
	 * 贪心:有点 dp+回溯的组合感觉
	 * @param l
	 */
	public void dp(List<List<Integer>> list,List<Integer> l,int[] candidates,int target,int e){
		if(target==0){
			list.add(new ArrayList(l));
			return;//6.得到想要的结果,回溯结束
		}
		if(target<candidates[0])return;//5.提前结束回溯

		for (int a = e;a >= 0  ; a--) {
			if(candidates[a]>target)continue;//4.优化:太大连回溯都不值得,
			l.add(candidates[a]);//1.dosomething
			dp(list,l,candidates,target-candidates[a],a);//2.recur
			l.remove(l.size()-1);//3.backTrace
		}
	}
}
